﻿#pragma once
#include "Index.h"

class INumArray:public IArrayRangeSum
{
public:
	/**
	 * 区域和检索-数组不可变
	 * 题目:https://leetcode.cn/problems/range-sum-query-immutable/
	 * 题解:https://leetcode.cn/problems/range-sum-query-immutable/solution/qu-yu-he-jian-suo-shu-zu-bu-ke-bian-by-l-px41/
	 * 数组 前缀和
	 *
	 * 给定一个整数数组  nums，处理以下类型的多个查询:
     * 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
	 * 实现 NumArray 类：
	 * NumArray(int[] nums) 使用数组 nums 初始化对象
	 * int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，
	 * 包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )
	 */
    virtual void initNums(const std::vector<int>& nums) = 0;
    virtual int sumRange(int left, int right) = 0;
};

class NumArray
{
public:
    class RangeSum:public INumArray
    {
    public:
        RangeSum() = default;
        RangeSum(std::vector<int>& nums)
        {
            initNums(nums);
        }

        std::shared_ptr<IArrayRangeSum> clone() override
        {
            return std::make_shared<RangeSum>();
        }
        void initNums(const std::vector<int>& nums) override
        {
            _accSume.clear();
            if (nums.empty())
                return;

            const int numsSize = nums.size();
            _accSume.resize(numsSize, 0);
            _accSume.front() = nums.front();

            for (int i = 1; i < numsSize; ++i)
                _accSume[i] = _accSume[i - 1] + nums[i];
        }
        int sumRange(int left, int right) override
        {
            const int leftSum = left - 1 >= 0 ? _accSume[left - 1] : 0;
            const int rightSum = _accSume[right];
            return rightSum - leftSum;
        }
    private:
        std::vector<int> _accSume;
    };
    class LaziedRangeSum:public INumArray
    {
    public:
    	std::shared_ptr<IArrayRangeSum> clone() override
    	{
            return std::make_shared<LaziedRangeSum>();
    	}
	    void initNums(const std::vector<int>& nums) override
	    {
            _accSize = 0;
            //前缀和数组大小为 numsSize+1,多出首个元素为0，可以简化后缀区间求和的计算
            _accSum.resize(1, 0);
            _nums = nullptr;

            if (nums.empty())
                return;
            _nums = &nums;
	    }
	    int sumRange(int left, int right) override
	    {
            //前缀和不够时再进行计算
		    while(_accSize<=right)
                _accSum.emplace_back(_accSum.back()+ _nums->at(_accSize++));

            //注意索引的位置要往后移1位
            return _accSum[right+1] - _accSum[left];
	    }
    private:
        int _accSize;
        std::vector<int> _accSum;
		const std::vector<int>* _nums;
    };

	class Review:public INumArray
	{
	public:
		std::shared_ptr<IArrayRangeSum> clone() override
		{
            return std::make_shared<Review>();
		}
		void initNums(const std::vector<int>& nums) override
		{
            _numsSize = nums.size();
            _preSums.resize(_numsSize + 1, 0);

            //前缀和数组初始化
            for (int i = 1; i <= _numsSize; ++i)
                _preSums[i] = _preSums[i - 1] + nums[i - 1];

            //std::cout << "pre sum made:" << TestingUtil::dumpFormatedValues(_preSums) << std::endl;
		}
		int sumRange(int left, int right) override
		{
            if (left < 0 || right<0 || left>right || right >= _numsSize)
                throw "invalid index";
            return _preSums[right+1] - _preSums[left];
		}
    private:
        int _numsSize;
        std::vector<int> _preSums;
	};
};
IArrayRangeSum* ArrayRangeSumFactory = new NumArray::LaziedRangeSum();

#ifdef DEV_DEBUG
#include <gtest/gtest.h>
TEST(NumsArrayTest, sumRange)
{
    TEST_SOLUTION2(INumArray, NumArray::LaziedRangeSum, NumArray::Review, &)
    {
        __slnTestor.setTestTimes(10,"small");
        __slnTestor.setTestingModeSetting("num_size", 10, "small");
        __slnTestor.setTestingModeSetting("num_min", 0, "small");
        __slnTestor.setTestingModeSetting("num_max", 10, "small");
        __slnTestor.setTestingModeSetting("sum_times", 100, "small");

        __slnTestor.setTestTimes(100, "large");
        __slnTestor.setTestingModeSetting("num_size", 1000, "large");
        __slnTestor.setTestingModeSetting("num_min", -1000, "large");
        __slnTestor.setTestingModeSetting("num_max", 1000, "large");
        __slnTestor.setTestingModeSetting("sum_times", 1000, "large");

        const std::string testing_mode = __slnTestor.getInTestingInfo().TestingMode;
        const int numsSize = __slnTestor.getTestingModeSetting<int>("num_size", testing_mode);
        const int numMin = __slnTestor.getTestingModeSetting<int>("num_min", testing_mode);
        const int numMax = __slnTestor.getTestingModeSetting<int>("num_max", testing_mode);
        const int rangeSumTimes = __slnTestor.getTestingModeSetting<int>("sum_times", testing_mode);
            
        std::vector<int> nums = TestingUtil::randRangeInts(numsSize, numMin, numMax);
        solution->initNums(nums);
        for (int i = 0; i < rangeSumTimes; ++i)
        {
            const int left = TestingUtil::randIndexInSize(nums.size());
            const int right = left + TestingUtil::randIndexInSize(nums.size() - left - 1);

            int expectSum = 0;
            for (int k = left; k <= right; ++k)
                expectSum += nums[k];

            const int rangeSum = solution->sumRange(left, right);

            ASSERT_EQ(rangeSum, expectSum)
                << "nums=" << FormatedUtil::dumpFormated(nums) << std::endl
                << "left=" << left << std::endl
                << "right=" << right << std::endl;
        }
    };
}
#endif